import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.trap1(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println(s.trap1(new int[]{4,2,0,3,2,5}));
    }
}

//第二次做
class Solution {
    /**
     * 单调栈
     * @param height
     * @return
     */
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = height[stack.peek()];
                ans += (Math.min(left, height[i]) - height[top]) * (i - stack.peek() - 1);
            }
            stack.push(i);
        }
        return ans;
    }

    /**
     * 双指针
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        int ans = 0;
        int i = 0, j = height.length - 1;
        int leftMax = height[i], rightMax = height[j];
        while (i < j) {
            if (leftMax < rightMax) {
                i++;
                if (height[i] <= leftMax) {
                    ans += leftMax - height[i];
                } else {
                    leftMax = height[i];
                }
            } else {
                j--;
                if (height[j] <= rightMax) {
                    ans += rightMax - height[j];
                } else {
                    rightMax = height[j];
                }
            }
        }
        return ans;
    }
}


//官方题解方法，动态规划
class Solution2_1 {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        for(int i = 1; i < height.length; i++){
            leftMax[i] = Math.max(height[i - 1], leftMax[i - 1]);
            int j = height.length - i - 1;
            rightMax[j] = Math.max(height[j + 1], rightMax[j + 1]);
        }

        int ans = 0;
        for(int i = 0; i < height.length; i++){
            if(leftMax[i] > height[i] && rightMax[i] > height[i]){
                ans += Math.min(leftMax[i], rightMax[i]) - height[i];
            }
        }
        return ans;
    }
}


//官方动态规划改进：双指针，常数空间
class Solution2_2 {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        int ans = 0;
        while(left <= right){
            if(height[left] < height[right]){
                if(height[left] <= leftMax){
                    ans += leftMax - height[left];
                }
                leftMax = Math.max(leftMax, height[left]);
                left++;
            }
            else{
                if(height[right] <= rightMax){
                    ans += rightMax - height[right];
                }
                rightMax = Math.max(rightMax, height[right]);
                right--;
            }
        }
        return ans;
    }
}


//官方解法，单调栈
class Solution2_3 {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for(int i = 0; i < height.length; i++){
            while(!stack.empty() && height[stack.peek()] < height[i]){
                int top = stack.pop();
                if(stack.empty()){
                    break;
                }

                int width = i - stack.peek() - 1;
                int depth = Math.min(height[i], height[stack.peek()]) - height[top];
                ans += width * depth;
            }
            stack.push(i);
        }
        return ans;
    }
}